NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/12906

Internet Message Format | 1996-08-05 | 1.6 KB

Path: EU.net!sun4nl!xs4all!falstaff
From: [e-mail] (Falstaff)
Newsgroups: comp.lang.c
Subject: Re: fast find algorithm
Date: 3 Apr 1996 14:13:49 GMT
Organization: XS4ALL, networking for the masses
Message-ID: <4ju12t$[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: xs1.xs4all.nl
X-Newsreader: NN version 6.5.0 #666 (NOV)

[e-mail] ("Stephen Etheridge") writes:

>Hi

>Does anyone have an search algoritm faster than a binary chop for the
>following:

>find a date from a sorted array of 1500 possible storage locations

It is theoretically not possible to find an entry in a sorted list
in less than ceil(2log(N)) (=11 in this case) operations.  bsearch()
does just that, so if it isn't fast enough you should try other methods.

A plain table lookup is fastest, but can only be done if the number
of elements isn't too great -- would not work for dates unless you
aren't interested in the year part, or if you have tons of memory
(need 31*12*100 elements if you ignore the century).

Hashing is slightly slower than straight table lookup and can't be
used when you want to delete elements from your table.

If you want to minimize time to *successfully* searching elements,
and a few elements account for>90% of your input, you can sort the
array into order of searches and use a linear search.

Frank
--
The famous GIICM now on line:  http://www.xs4all.nl/~falstaff/GIICM.html
------------------------------------------------------------------------
Frank A. Vorstenbosch        [phone]        [e-mail]